<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <div>
      <h1>
        给定一个包含 n
        个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素
        a，b，c 和 d ，使得 a + b + c +
        d 的值与 target 相等？找出所有满足条件且不重复的四元组。
      </h1>

      注意：答案中不可以包含重复的四元组。 <br />示例 <br />1： <br />输入：nums
      = [1,0,-1,0,-2,2], target = 0
      <br />输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 示例
      <br />
      2： 输入：nums = [], target = 0
      <br />输出：[]   <br />提示： 0 <= nums.length <= 200 -109 <= nums[i] <=
      109 -109 <= target <= 109

      <br />
      来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum
      著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    </div>
    <script>
      /**
       * @param {number[]} nums
       * @param {number} target
       * @return {number[][]}
       */
      var fourSum = function (nums, target) {
        if (nums.length < 4) {
          return [];
        }
        nums.sort((a, b) => a - b);
        console.log(nums);
        let arr = [];
        for (let i = 0; i < nums.length - 3; ++i) {
          console.log("i: ", i);
          if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
          }
          for (let j = i + 1; j < nums.length - 2; j++) {
            console.log("-- j: ", j);
            if (j > i + 1 && nums[j] == nums[j - 1]) {
              continue;
            }
            let l = j + 1;
            let r = nums.length - 1;
            console.log("  -- l: ", l);
            console.log("  -- r: ", r);
            while (l < r) {
              console.log("  ==  ", i, j, l, r);
              let sum = nums[i] + nums[j] + nums[l] + nums[r];
              if (sum == target) {
                //存入
                arr.push([nums[i], nums[j], nums[l], nums[r]]);
                //去重
                while (l < r && nums[l] == nums[l + 1]) {
                  l++;
                }
                while (l < r && nums[r] == nums[r - 1]) {
                  r--;
                }
                l++;
                r--;
              } else if (sum > target) {
                r--;
              } else {
                l++;
              }
            }
          }
        }
        return arr;
      };
      console.log(fourSum([1, 0, -1, 0, -2, 2, -3, 2], 0));
    </script>
  </body>
</html>
